package sort;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class QuickSort {  // 快速排序 最好：* O(N*logN) ---------最坏：O(n^2) 有序或逆序
    public static void main(String[] args) { // 空间复杂度 最好：O(logN) 最坏：O(n)
        int[] array = {27,15,19,28,68,6};
        int[] array1 = {27,15,19,28,68,6};

        quickSort1(array1);
        long startTime = System.currentTimeMillis();
        quickSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(array1));
    }
    public static void quickSort(int[] array){   // 递归实现
        quick(array, 0, array.length - 1);
    }
    public static void quick(int[] array, int start, int end){  // 递归左右
        if(start >= end){
            return;
        }
        // 小区间插入排序 减少递归次数
        if(end - start + 1 <= 14) {
            insert(array, start, end);
            return;
        }
        // 三数取中法
        int index = middleThree(array, start, end);
        Swap.swap(array,start,index);
        int pivot = chose1(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }
    private static int middleThree(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            } else if(array[mid] > array[right]){
                return right;
            } else {
                return mid;
            }
        } else if(array[mid] > array[left]){
            return left;
        } else if(array[mid] > array[right]){
            return mid;
        } else {
            return right;
        }
    }
    public static void insert(int[] array, int left, int right){
        for (int i = left + 1; i <= right; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= left ; j--) {
                if(array[j] > temp){
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = temp;
        }
    }
    public static int chose(int[] array, int left, int right){ //寻找基准放置的位置 挖坑法
        int temp = array[left];
        while (left < right){
            while (left < right && array[right] >= temp){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= temp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = temp;
        return left;
    }
    public static int chose1(int[] array, int left, int right) { // 寻找基准 Hoare 法
        int temp = array[left];
        int i = left;
        while (left < right){
            while (left < right && array[right] >= temp){
                right--;
            }
            while (left < right && array[left] <= temp){
                left++;
            }
            Swap.swap(array, left, right);
        }
        Swap.swap(array,left,i);
        return left;
    }
    public static void quickSort1(int[] array){  // 非递归实现 用栈
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = chose(array,left,right);
        if(pivot > left + 1){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot < right - 1){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = chose(array,left,right);
            if(pivot > left + 1){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right - 1){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }

}
